package com.kehao.leetcode.middle.tree_graph;

import org.junit.Test;

import java.util.*;

public class ZigzagLevelOrderSolution {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> floorQueue = new LinkedList<>();
        if(root!=null){
            queue.offer(root);
        }
        floorQueue.offer(0);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            Integer floor = floorQueue.poll();
            putTreeNode(poll,floor,map);
            if (poll.left!=null){
                queue.offer(poll.left);
                floorQueue.offer(floor+1);
            }
            if(poll.right!=null){
                queue.offer(poll.right);
                floorQueue.offer(floor+1);
            }
        }

        for (int i = 0; i < map.size(); i++) {
            List<Integer> list = map.get(i);
            if(i%2!=0){
                Collections.reverse(list);
            }
            result.add(list);
        }

        return result;
    }

    private void putTreeNode(TreeNode treeNode, int floor, HashMap<Integer, List<Integer>> map) {
        List<Integer> list ;
        if(map.containsKey(floor)){
            list = map.get(floor);
        }else {
            list = new LinkedList<>();
            map.put(floor,list);
        }
        list.add(treeNode.val);
    }

    @Test
    public void test01(){
        TreeNode treeNode3 = new TreeNode(3);
        treeNode3.left = new TreeNode(9);
        TreeNode treeNode20 = new TreeNode(20);
        treeNode3.right = treeNode20;
        treeNode20.left = new TreeNode(15);
        treeNode20.right = new TreeNode(7);

        List<List<Integer>> lists = zigzagLevelOrder(treeNode3);
        System.out.println(lists);
    }


}
